import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-21
 * Time: 11:11
 */

//622.设计循环队列
public class MyCircularQueue {
    public int[] elem;
    public int front;//队头下标
    public int rear;//队尾下标

    public MyCircularQueue(int k) {
        this.elem = new int[k + 1];//由于要牺牲一个空间，故长度应设置为k + 1
    }

    public boolean enQueue(int value) {
        if (isFull()){//调用函数，判满入队，因为是数组
            return false;
        }
        this.elem[rear] = value;//入队
        rear = (rear + 1) % elem.length;//移动
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()){//调用函数，判空出队
            return false;
        }
        front = (front + 1) % elem.length;//只需移动即可，后续元素会被自然入队覆盖掉
        return true;
    }

    public int Front() {
        if (isEmpty()){//判空
            return -1;
        }
        return elem[front];//直接根据下标获取
    }

    public int Rear() {
        //由于我们是多了一个傀儡空间，故获取队尾是获取其上一个元素
        if (isEmpty()){//判空
            return -1;
        }
        if (rear == 0){//为0时同样也要考虑
            return elem[elem.length - 1];
        }else{//不为0时正常考虑
            return elem[rear - 1];
        }
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        //直接返回其布尔值即可
        return  (this.rear + 1) % elem.length == front;
    }
}
//255.队列实现栈 - 双端
class MyStack1 {

    Deque<Integer> dq;

    public MyStack1() {
        dq = new LinkedList<>();
    }

    public void push(int x) {
        dq.offerLast(x);
    }

    public int pop() {
        return dq.pollLast();
    }

    public int top() {
        return dq.getLast();
    }

    public boolean empty() {
        return dq.isEmpty();
    }
}

class MyStack2 {

    Queue<Integer> dq1,dq2;

    public MyStack2() {
        dq1 = new LinkedList<>();
        dq2 = new LinkedList<>();
    }

    public void push(int x) {
        if (dq2.isEmpty()){
            dq1.offer(x);
        } else{
            dq2.offer(x);
        }
    }

    public int pop() {
        if (dq2.isEmpty()){
            while (dq1.size() - 1 != 0){
                dq2.offer(dq1.poll());
            }
            return dq1.poll();
        }else{
            while (dq2.size() - 1 != 0){
                dq1.offer(dq2.poll());
            }
            return dq2.poll();
        }
    }

    public int top() {
        int num = pop();
        if (dq2.isEmpty()){
            dq1.offer(num);
        }else{
            dq2.offer(num);
        }
        return num;
    }

    public boolean empty() {
        return dq1.isEmpty() && dq2.isEmpty();
    }
}

//232.栈实现队列
class MyQueue1 {

    Deque<Integer> dq;
    public MyQueue1() {
        dq = new LinkedList<>();
    }

    public void push(int x) {
        dq.offerLast(x);
    }

    public int pop() {
        return dq.pollFirst();
    }

    public int peek() {
        return dq.getFirst();
    }

    public boolean empty() {
        return dq.isEmpty();
    }
}

class MyQueue2 {

    Stack<Integer> dq1, dq2;
    public MyQueue2() {
        dq1 = new Stack<>();
        dq2 = new Stack<>();
    }

    public void push(int x) {
        dq1.push(x);
    }

    public int pop() {
        if (dq2.empty()){
            while (dq1.size() != 0){
                dq2.push(dq1.pop());
            }
            return dq2.pop();
        }else{
            return dq2.pop();
        }
    }

    public int peek() {
        int num = pop();
        dq2.push(num);
        return num;
    }

    public boolean empty() {
        return dq1.empty() && dq2.empty();
    }
}